/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-03
 * Time: 23:35
 */

public class Solution {



    // 方法一:
    // 递归回溯
    // 注意这里必须所有的数字都用上, 不是说半路运算的结果已经等于 target 直接就能返回了
    // public int result;
    // public void dfs(int[] arr, int index, int target){
    //     if(index==arr.length){
    //         if(target==0){
    //             result++;
    //             return;
    //         }
    //     }else{
    //         dfs(arr, index+1, target-arr[index]);
    //         dfs(arr, index+1, target+arr[index]);
    //     }
    // }
    // public int findTargetSumWays(int[] nums, int target) {
    //     dfs(nums, 0,target);
    //     return result;
    // }






    // 方法二:
    // DP
    // pos-neg=target
    // pos+neg=sum
    // target 和 sum 都很容易获得
    // 所以可得 neg = (sum-target)/2
    // 如果 neg 不是偶数, 说明根本找不到满足条件的表达式
    // 否则能找到, 题目转化为, 找到 几个数 使其和为 neg

    // dp[i][j]  表示前 i 个元素中, 和为 j 的表达式的数目
    // 所以每一维度都要多开辟一个
    // nums[i]>j , 不能选当前值, 只能与dp[i-1][j] 一样
    // nums[i]<=j, 说明可以选当前值, 并且结果增加了
    // 前i-1 个数目中可以选出dp[i-1][j] 个表达式
    // 增加 num[i] 之后, 又增加几个他们是 dp[i-1][j-nums[i]]
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0; // 数组的元素和
        for(int x: nums){
            sum+=x;
        }
        int differ=sum-target;
        // 因为 sum必须大于target, 并且target必须为整数
        if(differ<0||differ%2!=0){
            return 0;
        }
        int neg=differ/2; // neg 表示前面加上 - 的整数的和
        int len=nums.length;
        // dp[i][j], 前i个元素, 和为j的方案数
        int[][] dp=new int[len+1][neg+1]; // 因为 最后结果为 dp[len][neg], 所以都要+1
        dp[0][0]=1; // 前 0 个元素只有和为 0, 为1, 其他全为 0
        for(int i=1;i<=len;i++){
            for(int j=0;j<=neg;j++){
                if(j<nums[i-1]){
                    // 如果 j < nums[i], 只能不选
                    dp[i][j]=dp[i-1][j];
                }else{
                    // 如果 j >= nums[i], 可以选, 也可以不选
                    dp[i][j]=dp[i-1][j] + dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[len][neg];
    }
}
